/*
*
如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。

给你一个 正 整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。

示例 1：

输入：n = 20
输出：19
解释：1 到 20 之间所有整数除了 11 以外都是特殊整数。所以总共有 19 个特殊整数。
示例 2：

输入：n = 5
输出：5
解释：1 到 5 所有整数都是特殊整数。
示例 3：

输入：n = 135
输出：110
解释：从 1 到 135 总共有 110 个整数是特殊整数。
不特殊的部分数字为：22 ，114 和 131 。

提示：

1 <= n <= 2 * 109

  - @author ala
  - @date 2024-09-20 08:18
*/
package main

import (
	"fmt"
	"strconv"
)

func main() {
	n := 20

	fmt.Println(countSpecialNumbers(n))
}

/**
 *	数位dp
 */
func countSpecialNumbers(n int) int {
	nums = toNums(n)
	N = len(nums)

	//	一定有更简便的方法，不然go对数组太不友好了
	memo = make([][][]int, N)
	for i := range memo {
		memo[i] = make([][]int, 1<<10)
		for j := range memo[i] {
			memo[i][j] = make([]int, 4)
			for k := range memo[i][j] {
				memo[i][j][k] = -1
			}
		}
	}

	return f(0, 0, true, false)
}

var N int
var nums []int

/**
 *	转为int切片
 */
func toNums(n int) []int {
	str := strconv.Itoa(n)
	nums := make([]int, len(str))
	for i := 0; i < len(str); i++ {
		num := str[i] - '0'
		nums[i] = int(num)
	}
	return nums
}

/**
 *	记忆搜
 */
var memo [][][]int

func f(i, mark int, isLimit, isNum bool) int {
	if i >= N {
		if isNum {
			return 1
		} else {
			return 0
		}
	}

	//	go 就没有三目运算符吗。。。
	kl := 0
	if isLimit {
		kl = 2
	}
	kn := 0
	if isNum {
		kn = 1
	}
	key := kl | kn
	res := memo[i][mark][key]
	if res != -1 {
		return res
	}

	res = 0
	if !isNum {
		res += f(i+1, mark, false, false)
	}

	up := 9
	if isLimit {
		up = nums[i]
	}
	down := 1
	if isNum {
		down = 0
	}

	for j := down; j <= up; j++ {
		if (mark >> j & 1) == 0 {
			res += f(i+1, mark|(1<<j), isLimit && j == up, true)
		}
	}

	memo[i][mark][key] = res
	return res
}
